package com.zlk.algorithm.algorithm.sort.heap;

import com.zlk.algorithm.algorithm.sort.SortUtils;
import org.junit.Test;

import java.util.Arrays;

/**
 * @program: algorithm
 * @ClassName HeapSort
 * @description: 大小堆构造，heapInsert   heapify   堆排序
 * 堆构造利用了完全二叉树的性质
 *   i位置  左子树位置  2i+1  右子树2i+2  父节点为（i-1）/2
 * @author: slfang
 * @create: 2024-01-23 10:38
 * @Version 1.0
 **/
public class HeapSort {

    @Test
    public void test1(){

//        int[] arr = new int[]{1,20,4,8,22,4};
//        //输出 1  取整
//        System.out.println(arr[-1/2]);
        int testTimes = 1000;
        int maxVal = 100;
        int maxLen = 30;
        for (int i = 0; i < testTimes; i++) {
            int[] randomArr = SortUtils.getRandomArr(maxVal, maxLen);
            int[] copyArr = Arrays.copyOf(randomArr, randomArr.length);
            Arrays.sort(randomArr);
            heapSort(copyArr);
            if(!SortUtils.isEqual(randomArr,copyArr)){
                System.out.println("fail");
                System.out.println("random:"+randomArr);
                System.out.println("copyArr:"+copyArr);
                return ;
            }
        }
        System.out.println("success!");
    }

    public void heapSort(int[] arr){
        if(arr.length<2||arr==null){
            return ;
        }
        int size = arr.length;
        //1、方法一 构建大堆  时间复杂度nlogn
        for (int i = 0; i < size; i++) {
            heapInsert(arr,i);
        }
        // 方法二  时间复杂度o(N)
        // 为何时间复杂度为N?
        // 从最底层heapify  最后一层是 n/2（节点树）+lonN(堆化操作)   n/4  n/8  n/16
        //                        o
        //                     o     o       n/4*2   （n/4代表节点数   2代表heapify只需要走二层）
        //                   0   0  o  o     n/2 * 1 （n/2代表节点数   1代表heapify只需要走一层）
        //
        // T(n)  =         n/2*1 +n/4*2+n/8*3+....
        // 2T(n) =      n+ n/2*2 +n/4*3+n/8*4
        // T(n) = n +n/2+n/4+n/8   等于数列
        //
//        for (int i = size-1; i >=0 ; i--) {
//            heapify(arr,i,size);
//        }
        //取第一位置与最后一个位置交换  然后  --size（索引从size-1 开始） 确定最后一个位置 然后heapify 然后重复上述操作
        //下列时间复杂度为 nlogn
        SortUtils.swap(arr,0,--size);
        while (size>0){
            heapify(arr,0,size);
            SortUtils.swap(arr,0,--size);
        }
    }

    /**
     * 刚来树下浮，由于index传值是0 所以每次都是从堆顶下来
     * @param arr
     * @param index
     * @param size
     */
    private void heapify(int[] arr, int index, int size) {
        int left  = (index<<1)+1;
        while (left<size){
            int right = left+1;
            int bigIndex = right<size&&arr[left]<arr[right]?right:left;
            bigIndex = arr[index]>arr[bigIndex]?index:bigIndex;
            if(bigIndex==index){
                break;
            }
            SortUtils.swap(arr,index,bigIndex);
            index = bigIndex;
            left = (index<<1)+1;
        }
    }



    /**
     * 刚来的树往上
     * @param arr
     * @param index
     */
    public void heapInsert(int[] arr,int index){
       while (arr[index]>arr[(index-1)/2]){
           SortUtils.swap(arr,(index-1)/2,index);
           index = (index-1)/2;
       }
    }

}
